/*
 * @lc app=leetcode.cn id=1631 lang=javascript
 *
 * [1631] 最小体力消耗路径
 */

// @lc code=start
/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function (heights) {
  let [m, n] = [heights.length, heights[0].length];
  const edges = [];

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      let idx = i * n + j;
      if (i > 0) {
        edges.push([idx, idx - n, Math.abs(heights[i][j] - heights[i - 1][j])]);
      }
      if (j > 0) {
        edges.push([idx, idx - 1, Math.abs(heights[i][j] - heights[i][j - 1])]);
      }
    }
  }
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(m * n);
  let result = 0;
  for (const edge of edges) {
    const [x, y, v] = [edge[0], edge[1], edge[2]];
    uf.union(x, y);
    if (uf.connected(0, m * n - 1)) {
      result = v;
      break;
    }
  }
  return result;
};

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n;
  }
  find(x) {
    if (x !== this.parent[x]) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    let [ux, uy] = [this.find(x), this.find(y)];
    if (ux === uy) {
      return false;
    }
    if (this.size[ux] > this.size[uy]) {
      [ux, uy] = [uy, ux];
    }
    this.parent[ux] = uy;
    this.size[uy] += this.size[ux];
    this.count--;
    return true;
  }
  connected(x, y) {
    const [ux, uy] = [this.find(x), this.find(y)];
    return ux === uy;
  }
}
// @lc code=end
